#ifndef RBTREE_H_INCLUDED
#define RBTREE_H_INCLUDED
#include "RBTreeNode.h"
#include"RBTreeIterator.h"

/**
 * 红黑树实现
 */
template<typename K, typename V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;

	typedef Node* ParentNode;

public:
	typedef RBTreeIterator<K, V> Iterator;

public:
	RBTree();
	Iterator begin();

	Iterator end();

	ParentNode& getRoot();

	std::pair<Iterator, bool> insertUnique(const std::pair<K, V>& data);
private:
	ParentNode pHead;
};

template<typename K, typename V>
RBTree<K, V>::RBTree() :pHead(new RBTree::Node())
{

}

template<typename K, typename V>
typename RBTree<K, V>::Iterator RBTree<K, V>::begin()
{
	return RBTree<K, V>::Iterator(this->pHead->left);
}

template<typename K, typename V>
typename RBTree<K, V>::Iterator RBTree<K, V>::end()
{
	return RBTree<K, V>::Iterator(this->pHead);
}


template<typename K, typename V>
typename RBTree<K, V>::ParentNode& RBTree<K, V>::getRoot()
{
	return this->pHead->parent;
}

template<typename K, typename V>
std::pair<typename RBTree<K, V>::Iterator, bool> RBTree<K, V>::insertUnique(const std::pair<K, V>& data)
{
	// 获取根节点
	ParentNode& root = this->getRoot();

	ParentNode newNode = nullptr;

	// 根节点为空
	if (root == nullptr)
	{
		newNode = root = new Node(data.first, data.second, BLACK);

		// 指向根节点
		root->parent = this->pHead;

	}
	else
	{
		ParentNode current = root;

		ParentNode parent = current;

		while (current)
		{
			// 找到 最底下的节点
			if (current->value.first < data.first)
			{
				parent = current;

				current = current->left;
			}
			else if (current->value.first > data.first)
			{
				parent = current;
				current = current->reight;
			}
		}
		newNode = current = new Node(data.first, data.second, BLACK);

		if (data.first < parent->value.first)
		{
			parent->left = current;
		}
		else
		{
			parent->reight = current;
		}

		current->parent = parent;

		return std::pair<typename RBTree<K, V>::Iterator, bool>(Iterator(current), true);
	}

	return std::pair<typename RBTree<K, V>::Iterator, bool>(Iterator(root), true);

}
#endif // RBTREE_H_INCLUDED
